import collections
from typing import List


class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0

        route_of_stop = collections.defaultdict(list)
        for rid, route in enumerate(routes):
            for stop in route:
                route_of_stop[stop].append(rid)

        visited_route = set()
        visited_stop = {source}
        queue = collections.deque([source])
        now = 0
        while queue:
            for _ in range(len(queue)):
                stop1 = queue.popleft()
                for rid in route_of_stop[stop1]:
                    if rid not in visited_route:
                        for stop2 in routes[rid]:
                            if stop2 == target:
                                return now + 1
                            if stop2 not in visited_stop:
                                queue.append(stop2)
                                visited_stop.add(stop2)
                    visited_route.add(rid)
            now += 1

        return -1


if __name__ == "__main__":
    # 2
    print(Solution().numBusesToDestination(routes=[[1, 2, 7], [3, 6, 7]],
                                           source=1, target=6))

    # -1
    print(Solution().numBusesToDestination(routes=[[7, 12], [4, 5, 15], [6], [15, 19], [9, 12, 13]],
                                           source=15, target=12))
